# 原始函数（有问题）
def find_duplicates_original(lst):
    result = []
    for i in range(len(lst)):
        for j in range(i+1, len(lst)):
            if lst[i] == lst[j]:
                result.append(lst[i])
    return result


# 改进版本1：效率优化 + 结果去重
def find_duplicates_v1(lst):
    """
    使用集合来追踪已见过的元素，时间复杂度 O(n)
    返回去重后的重复元素列表
    """
    seen = set()
    duplicates = set()
    
    for item in lst:
        if item in seen:
            duplicates.add(item)
        else:
            seen.add(item)
    
    return list(duplicates)


# 改进版本2：保持原始逻辑但结果去重
def find_duplicates_v2(lst):
    """
    使用集合来存储结果，避免重复添加
    时间复杂度仍为 O(n²)，但结果正确
    """
    result = set()
    for i in range(len(lst)):
        for j in range(i+1, len(lst)):
            if lst[i] == lst[j]:
                result.add(lst[i])
    return list(result)


# 改进版本3：返回所有重复项及其出现次数
def find_duplicates_v3(lst):
    """
    返回一个字典，包含所有重复元素及其出现次数
    """
    from collections import Counter
    counter = Counter(lst)
    return {item: count for item, count in counter.items() if count > 1}


# 测试代码
if __name__ == "__main__":
    # 测试用例1：元素出现3次
    test1 = [1, 1, 1]
    print(f"测试1: {test1}")
    print(f"原始函数结果: {find_duplicates_original(test1)}")  # 输出: [1, 1]
    print(f"改进v1结果: {find_duplicates_v1(test1)}")          # 输出: [1]
    print(f"改进v2结果: {find_duplicates_v2(test1)}")          # 输出: [1]
    print(f"改进v3结果: {find_duplicates_v3(test1)}")          # 输出: {1: 3}
    print()
    
    # 测试用例2：多个重复元素
    test2 = [1, 2, 3, 2, 4, 3, 3, 5]
    print(f"测试2: {test2}")
    print(f"原始函数结果: {find_duplicates_original(test2)}")  # 可能包含重复
    print(f"改进v1结果: {find_duplicates_v1(test2)}")          # 输出: [2, 3]
    print(f"改进v2结果: {find_duplicates_v2(test2)}")          # 输出: [2, 3]
    print(f"改进v3结果: {find_duplicates_v3(test2)}")          # 输出: {2: 2, 3: 3}
    print()
    
    # 测试用例3：无重复
    test3 = [1, 2, 3, 4, 5]
    print(f"测试3: {test3}")
    print(f"原始函数结果: {find_duplicates_original(test3)}")  # 输出: []
    print(f"改进v1结果: {find_duplicates_v1(test3)}")          # 输出: []
    print()

